/**
 * @author ChaP
 * @date 2019/05/18
 * @describe:
 */
package CodingTest.AC20190518;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**leetcode - 442
 * 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

 找到所有出现两次的元素。

 你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

 示例：

 输入:
 [4,3,2,7,8,2,3,1]

 输出:
 [2,3]
 */
public class findDuplicates {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
    for(int i =0;i<nums.length;i++){
        int num = Math.abs(nums[i]);
        if(nums[num-1] <=0){
            res.add(num);
        }else{
            nums[num-1]*=-1;
        }
    }
    return res;
    }

    public static void main(String[] args) {
        findDuplicates fd = new findDuplicates();
        int[] nums = {4,3,2,7,8,2,3,1};
        System.out.println(fd.findDuplicates(nums));
    }

}
